package leetcode_链表;

import general_class.ListNode;

import java.util.PriorityQueue;

/**
 * 合并 K 个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * 算法：堆、分治
 *
 * @author yzh
 * @version 1.0
 * @date 2022/3/20 21:30
 */
public class _23 {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (o1, o2) -> {
            if (o1.val < o2.val) return -1;
            else if (o1.val == o2.val) return 0;
            else return 1;
        });
        for (ListNode node : lists) if (node != null) queue.add(node);
        ListNode ans = new ListNode(0), p = ans;
        while (!queue.isEmpty()) {
            p.next = queue.poll();
            p = p.next;
            if (p.next != null) queue.add(p.next);
        }
        return ans.next;
    }


    public ListNode mergeKListsRecursion(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) return lists[l];
        int mid = l + (r - l) / 2;
        ListNode l1 = merge(lists, l, mid);
        ListNode l2 = merge(lists, mid + 1, r);
        return merge2Lists(l1, l2);
    }


    public ListNode mergeKListsIterator(ListNode[] lists) {
        if (lists.length == 0) return null;
        for (int i = 1; i < lists.length; i *= 2) mergePass(lists, i);
        return lists[0];
    }

    void mergePass(ListNode[] lists, int k) {
        int i = 0, n = lists.length;
        while (i + 2 * k - 1 < n) {
            lists[i] = merge2Lists(lists[i], lists[i + k]);
            i += 2 * k;
        }
        if (i + k - 1 < n - 1)
            lists[i] = merge2Lists(lists[i], lists[i + k]);
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0), cur = res;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return res.next;
    }

}
